//
//$Id: min_cover.h 687 2011-03-13 12:21:29Z Oleg.Bulychov $
#pragma once

#include "src/heo/include/random.h"
//#include "src/heo/include/calc_hash.h"
#include "src/heo/include/reflection.h"
#include "src/heo/include/solution.h"
#include "src/heo/include/optimization_direction.h"

#include "src/heo/include/transmit_matrix2d.h"
#include "src/heo/include/matrix2d.h"
#include "grids.h"
#include "solvers/shc/shc_common.h"

//class SubsetEx: public BitSet
//{
//    public Subset_Serializer* serializer_;
//};
//===============

namespace meta
{

template<>
struct is_visitable< BitSet >
{
    enum {result = 0};
};

}
template<class V>
struct transmit_handler<BitSet, V>
{
    static void visit(BitSet& s, V& v)
    {
        visit(s, v, meta::int2type<V::transmit_tag>());
    }

    static void visit(BitSet& s, V& bcast, meta::int2type<BCAST_TAG>)
    {
        if (bcast.is_Root())
        {
            visit(s, bcast, meta::int2type<SEND_TAG>());
        }
        else
        {
            visit(s, bcast, meta::int2type<RECV_TAG>());
        }
    }

    static void visit(BitSet& s, V& send, meta::int2type<SEND_TAG>)
    {
        BitSet_Serializer bss;//???????
        unsigned int len;
        byte_t* temp = s.serialize(bss, len);
        size_t dim = len;
        send << dim;
        bool prev = send.buffered_;
        send.buffered_ = true;
        send.visit_Array(temp, dim, "", 0);
        send.buffered_ = prev;
        delete[] temp;
    }

    static void visit(BitSet& s, V& recv, meta::int2type<RECV_TAG>)
    {
        size_t dim = 0;
        recv >> dim;
        byte_t* temp = new byte_t[dim];
        recv.visit_Array(temp, dim, "", 0);
        s.deserialize(temp);
        delete[] temp;
    }
};
//===============

struct MinCover_Config
{
    static char const* get_Name() { return "gridmin"; }
    static char const* get_Section() { return get_Name(); }

    template<class V>
    void accept(V& v)
    {
    }
};

//================================// 
// Problem, Solution, etc.        //
//================================//

struct MinCover_Problem
{
    static char const* get_Default_File_Name() { return NULL; }

    std::vector<Grid> const* pgrids_;
    Bool_Matrix const* pbm_;
    Subset_Matrix const* pcm_;
    u_t m_, n_, grids_num_, fixed_num_, var_num_;

    void init(std::vector<Grid> const* pgrids, u_t const fixed_num, Bool_Matrix const* pbm, Subset_Matrix const* pcm)
    {
        pgrids_    = pgrids;
        pbm_       = pbm;
        pcm_       = pcm;
        m_         = pbm->nrows_;
        n_         = pbm->ncols_;
        grids_num_ = pgrids->size();
        fixed_num_ = fixed_num;
        var_num_   = grids_num_ - fixed_num_;
    }
};

class MinCover_Solution
{
    //DISALLOW_COPY_AND_ASSIGN(GridMin_Solution);
public:
    typedef int                     TCostType;
    typedef minimization<TCostType> TDirection;
    typedef Matrix2D<u_t>           IntMatrix;
    
    BitSet    s_;
protected:
    TCostType cost_;
    bool      changed_;
    unsigned  hash_;
    bool      hash_changed_;
    
public:
    explicit MinCover_Solution():
        cost_(),
        changed_(),
        hash_(),
        hash_changed_()
    {}

    template<class E>
    void init(E* env, random_generator& rnd)
    {
        return;
    }

    template<class E>
    void generate(E* env, random_generator& rnd)
    {
        Bool_Matrix bm = *(env->problem_.pbm_);

        for (u_t i = 0; i < env->problem_.m_; ++i)
        {
            for (u_t j = 0; j < env->problem_.n_; ++j)
            {
                if (bm[i][j] == 1)
                {
                    u_t num = rnd.next_SizeT((*env->problem_.pcm_)[i][j].size());
                    u_t id  = (*env->problem_.pcm_)[i][j].get_By_Count(num);
                    s_.insert(id);
                    bm.cover((*env->problem_.pgrids_)[env->problem_.fixed_num_ + id]);
                }
            }
        }

        //#pragma omp critical
        //{
        //	cout << s_.to_String() << endl;
        //}

        changed_ = true;
    }

    TCostType get_Cost() const
    {
        ASSERT_(!changed_);
        return cost_;
    }

    unsigned get_Hash()
    {
        ASSERT_(!changed_);
        if (hash_changed_)
        {
            hash_changed_ = false;
            hash_ = s_.calc_Hash(); //TODO fix me: for GA
        }
        return hash_;
    }

    template<class E>
    void evaluate(E* env, random_generator& rnd)
    {
        if (!changed_)
        {
            return;
        }

        changed_ = false;
        hash_changed_ = true;

        cost_ = env->problem_.fixed_num_ + s_.size();
    }

    template<class V>
    void accept(V& v)
    {
        v(cost_);
        v(changed_);
        v(hash_);
        v(hash_changed_);
        v(s_);
    }

    void assign(MinCover_Solution const& sol)
    {
        changed_        = sol.changed_;
        cost_           = sol.cost_;
        hash_           = sol.hash_;
        hash_changed_   = sol.hash_changed_;
        s_              = sol.s_;
    }

    template<class X>
    void copy_To(X& x) const
    {
        x.assign(*this);
    }

    template<class E>
    void print(std::ostream& os, E* env) const
    {
        //PrintGridsSetTXT(os, *(env->problem_.pgrids_), s_);// old version
    }

    template<class E>
    static bool read(E* env, std::string const& file_name, Solution_Pool<MinCover_Solution>& pool)
    {
        return false;
    }

    template<class E>
    void write(E* env, std::string const& file_name, size_t id, size_t count) const
    {
    }
};

template<>
struct solution<MinCover_Solution, sa_tag>:
    public MinCover_Solution
{
public:
    template<class E>
    void move(E* env, random_generator& rnd, double probability)
    {
        double prob = 4.0 / env->problem_.var_num_;
		prob = (prob < 0.1 ? prob : 0.1);

        for (u_t i = 0; i < env->problem_.var_num_; ++i)
        {
            if (rnd.next_Double() < prob)
            {
                s_[i] = (s_[i] ? false : true);
            }
        }

        // correction
        Bool_Matrix   bm = *env->problem_.pbm_;
        
        for (BitSet::enumerator en = s_.first(); en != s_.end(); ++en)
        {
            bm.cover((*env->problem_.pgrids_)[env->problem_.fixed_num_ + *en]);
            if (bm.nones_ == 0)
            {
                break;
            }
        }

        if (bm.nones_ > 0)
        {
            for (u_t i = 0; i < env->problem_.m_; ++i)
            {
                for (u_t j = 0; j < env->problem_.n_; ++j)
                {
                    if (bm[i][j] == 1)
                    {
                        u_t num = rnd.next_SizeT((*env->problem_.pcm_)[i][j].size());
                        u_t id  = (*env->problem_.pcm_)[i][j].get_By_Count(num);
                        s_.insert(id);
                        bm.cover((*env->problem_.pgrids_)[env->problem_.fixed_num_ + id]);
                    }
                }
            }
        }
    }
};

template<>
struct solution<MinCover_Solution, ga_tag>:
    public MinCover_Solution
{
public:
    mutable double wheel_sector_;

    // simple one-point crossover without feasibility validation
    template<class E>
    void cross(E* env, random_generator& rnd, solution<MinCover_Solution, ga_tag>& genome)
    {
        u_t j = rnd.next_SizeT(env->problem_.var_num_);
        for (u_t i = j; i < env->problem_.var_num_; ++i)
        {
            swap(s_[i], genome.s_[i]);
        }
        changed_ = genome.changed_ = true;
    }

    // mutation a la move in SA + feasibility correction
    template<class E>
    void mutate(E* env, random_generator& rnd, double mutationProbability)
    {
        double prob = 4.0 / env->problem_.var_num_;
		prob = (prob < 0.1 ? prob : 0.1);

        // mutation
        for (u_t i = 0; i < env->problem_.var_num_; ++i)
        {
            if (rnd.next_Double() < prob)
            {
                s_[i] = (s_[i] ? false : true);
            }
        }

        // correction
        Bool_Matrix   bm = *env->problem_.pbm_;
        
        for (BitSet::enumerator en = s_.first(); en != s_.end(); ++en)
        {
            bm.cover((*env->problem_.pgrids_)[env->problem_.fixed_num_ + *en]);
            if (bm.nones_ == 0)
            {
                break;
            }
        }

        if (bm.nones_ > 0)
        {
            for (u_t i = 0; i < env->problem_.m_; ++i)
            {
                for (u_t j = 0; j < env->problem_.n_; ++j)
                {
                    if (bm[i][j] == 1)
                    {
                        u_t num = rnd.next_SizeT((*env->problem_.pcm_)[i][j].size());
                        u_t id  = (*env->problem_.pcm_)[i][j].get_By_Count(num);
                        s_.insert(id);
                        bm.cover((*env->problem_.pgrids_)[env->problem_.fixed_num_ + id]);
                    }
                }
            }
        }
    }

    TCostType get_Fitness() const { return get_Cost(); }
};

template<>
struct solution<MinCover_Solution, shc_tag>:
    public MinCover_Solution
{
    typedef solution<MinCover_Solution, shc_tag> MinCover_Solution_SHC;
public:
    template<class E>
    void move(E* env, random_generator& rnd, double probability)
    {
        double prob = 4.0 / env->problem_.var_num_;
		prob = (prob < 0.1 ? prob : 0.1);
        for (u_t i = 0; i < env->problem_.var_num_; ++i)
        {
            if (rnd.next_Double() < prob)
            {
                s_[i] = (s_[i] ? false : true);
            }
        }

        // correction
        Bool_Matrix   bm = *env->problem_.pbm_;
        
        for (BitSet::enumerator en = s_.first(); en != s_.end(); ++en)
        {
            bm.cover((*env->problem_.pgrids_)[env->problem_.fixed_num_ + *en]);
            if (bm.nones_ == 0)
            {
                break;
            }
        }

        if (bm.nones_ > 0)
        {
            for (u_t i = 0; i < env->problem_.m_; ++i)
            {
                for (u_t j = 0; j < env->problem_.n_; ++j)
                {
                    if (bm[i][j] == 1)
                    {
                        u_t num = rnd.next_SizeT((*env->problem_.pcm_)[i][j].size());
                        u_t id  = (*env->problem_.pcm_)[i][j].get_By_Count(num);
                        s_.insert(id);
                        bm.cover((*env->problem_.pgrids_)[env->problem_.fixed_num_ + id]);
                    }
                }
            }
        }
    }
};


//EOF!
